package search;

public class BinarySearch {
    // 实现一：迭代版

    /**
     *
     * 二分查找
     *
     * 也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；
     * 若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
     *
     *
     * 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。
     * 但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
     * @param a 给定数组
     * @param value 目标值
     * @return
     */
    public static int BinarySearch(int a[], int value) {
        int low = 0;
        int high = a.length-1;
        int mid = 0;
        while (low <= high)
        {
            mid = low + (high - low) /2;
            if(a[mid] == value) {
                return mid;
            }
            if(a[mid] > value) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return -1; //return low 应该插入的位置
    }

    // 实现二：递归版

    /**
     *
     * @param nums
     * @param target
     * @param low
     * @param high
     * @return
     */
    public int binarySearchRecur(int[] nums, int target, int low, int high) {
        if (low > high) { return low; } //base case
        int mid = low + (high - low) / 2;
        if (nums[mid] > target) {
            return binarySearchRecur(nums,target,low,mid-1);
        } else if (nums[mid] < target) {
            return binarySearchRecur(nums,target,mid+1,high);
        } else {
            return mid;
        }
    }
    //含有重复数字的情况
//主要区别：等于mid也要将high-1；直到low>high结束，返回low（其实是高位，重复数字的第一位）
    public static int BinarySearchDuplicate(int a[], int value, int n) {
        int low = 0;
        int high = n-1;
        int mid = 0;
        while (low <= high) {
            mid = low + (high - low) * 1/2;
            if(a[mid] >= value) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
    //含有重复数字：递归版
    public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
        if (low > high) { return low; }
        int mid = low + (high - low) / 2;
        if (nums[mid] < target) {
            return firstOccurrenceRecur(nums,target,mid + 1,high);
        } else {
            return firstOccurrenceRecur(nums,target,low,mid-1);
        }
    }
}
